/**
 * 取出大顶堆堆顶元素
 * 入参是索引，表示堆结点索引的下界、上界
 * @param {number} low
 * @param {number} high
 */
// function downHeap(low, high) {
//   let i = low // 初始化i为堆顶结点
//   let j = i * 2 + 1 // 初始化j为栈堆结点的左孩子
//   while (j <= high) {
//     // 如果右孩子比做孩子更大，则用右结点和根节点比较
//     if (j + 1 <= hight && heap[j + 1] > heap[j]) {
//       j = j + 1
//     }

//     // 如果当前结点比孩子结点小，则交换两者的位置，把较大的结点送到上面
//     if (heap[i] < heap[j]) {
//       // 交换位置
//       const temp = heap[i] // 保留一份根结点
//       heap[i] = heap[j]
//       heap[j] = temp

//       i = j // 更新根结点索引
//       j = j * 2 + 1 // 更新左孩子结点索引
//     } else {
//       break
//     }
//   }
// }

/**
 * 取出小顶堆堆顶元素
 * 入参是索引，表示堆结点索引的下界、上界
 * @param {number} low
 * @param {high} hight
 */
function downHeap(low, high) {
  let i = low // 初始化i为堆顶结点
  let j = i * 2 + 1 // 初始化j为堆顶结点的左孩子
  while (j <= high) {
    // 如果右孩子比做孩子更大，则用右结点和根节点比较
    if (j + 1 <= hight && heap[j + 1] > heap[j]) {
      j = j + 1
    }

    // 如果当前结点比孩子结点小，则交换两者的位置，把较大的结点送到上面
    if (heap[i] < heap[j]) {
      // 交换位置
      const temp = heap[i] // 保留一份根结点
      heap[i] = heap[j]
      heap[j] = temp

      i = j // 更新根结点索引
      j = j * 2 + 1 // 更新左孩子结点索引
    } else {
      break
    }
  }
}

/**
 * 往大顶堆里插入一个元素
 * 入参是索引，表示堆结点索引的下界、上界
 * @param {number} low
 * @param {number} high
 */
// function upHead(low, high) {
//   let i = high // 初始化i（当前结点索引）为第一个可插入位置
//   let j = Math.floor((i - 1) / 2) // 初始化j为i的父结点
//   // 没有对比到堆顶
//   while (j >= low) {
//     // 如果当前结点比父结点大
//     if (heap[i] > heap[j]) {
//       // 交换当前结点和父结点
//       const temp = heap[i]
//       heap[i] = heap[j]
//       heap[j] = temp

//       i = j // 更新当前结点索引
//       j = Math.floor((i - 1) / 2) // 更新父结点索引
//     } else {
//       break // 比对完成，终止程序
//     }
//   }
// }

/**
 * 往小顶堆里插入一个元素
 * 入参是索引，表示堆结点索引的下界、上界
 * @param {number} low
 * @param {number} high
 */
function upHead(low, high) {
  let i = high // 初始化i（当前结点索引）为第一个可插入位置
  let j = Math.floor((i - 1) / 2) // 初始化j为i的父结点
  // 没有对比到堆顶
  while (j >= low) {
    // 如果当前结点比父结点小
    if (heap[i] < heap[j]) {
      // 交换当前结点和父结点
      const temp = heap[i]
      heap[i] = heap[j]
      heap[j] = temp

      i = j // 更新当前结点索引
      j = Math.floor((i - 1) / 2) // 更新父结点索引
    } else {
      break // 比对完成，终止程序
    }
  }
}
